// https://leetcode.cn/problems/longest-palindromic-substring/description/

// 算法思路总结：
// 1. 使用动态规划寻找最长回文子串
// 2. dp[i][j]记录子串s[i..j]是否为回文
// 3. 从后往前遍历，实时更新最长回文子串
// 4. 时间复杂度：O(n²)，空间复杂度：O(n²)

#include <iostream>
using namespace std;

#include <string>
#include <vector>
#include <algorithm> 

class Solution 
{
public:
    string longestPalindrome(string s) 
    {
        int m = s.size(), ret = 0;
        string res;
        vector<vector<bool>> dp(m, vector<bool>(m, false));

        for (int i = m - 1 ; i >= 0 ; i--)
        {
            for (int j = i ; j < m ; j++)
            {
                if (s[i] == s[j])
                {
                    if (i == j)
                        dp[i][j] = true;
                    else if (i + 1 == j)
                        dp[i][j] = true;
                    else
                        dp[i][j] = dp[i + 1][j - 1];
                }
                if (dp[i][j] && j - i + 1 > ret) 
                {
                    res = s.substr(i, j - i + 1);
                    ret = j - i + 1;
                }
            }
        }
        return res;
    }
};

int main()
{
    string s1 = "babad", s2 = "cbbd";
    Solution sol;

    cout << sol.longestPalindrome(s1) << endl;
    cout << sol.longestPalindrome(s2) << endl;

    return 0;
}